package com.future;

/**
 * Description: 421. ��������������������ֵ
 * ����һ���������� nums ������ nums[i] XOR nums[j] ����������������� 0 �� i �� j < n ��
 * <p>
 * ���ף�������� O(n) ��ʱ�������������
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺nums = [3,10,5,25,2,8]
 * �����28
 * ���ͣ������������ 5 XOR 25 = 28.
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/4/19 14:20
 */
public class Solution_421 {

    public static void main(String[] args) {
      /*  System.out.println(Integer.toBinaryString(10));
        for (int i = 3; i >= 0; i--) {
            System.out.println((10 >> i) & 1);
        }*/
        int[] arr = {3, 10, 5, 25, 2, 8};
        arr = new int[]{1};
        int maximumXOR = findMaximumXOR(arr);

        System.out.println(maximumXOR);
    }

    public static class Node {
        public Node[] nexts = new Node[2];
    }

    /**
     * �����߶���
     */
    public static class NumTrie {
        public Node head = new Node();

        public void add(int newNum) {
            Node cur = head;
            for (int move = 31; move >= 0; move--) {
                /**
                 * ȡ��moveλ�õ�ֵ��0����1
                 */
                int path = ((newNum >> move) & 1);
                cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
                cur = cur.nexts[path];
            }
        }

        public int maxXor(int sum) {

            Node cur = head;
            int res = 0;
            for (int move = 31; move >= 0; move--) {
                /**
                 * ȡsum��moveλ�õ�ֵ��0����1
                 */
                int path = (sum >> move) & 1;
                /**
                 * ��λ31λ���Ƿ���λ
                 * path ^ 1��pathȡ������Ϊ���������ֻ�ͣ�̰����best
                 */
                int best = move == 31 ? path : (path ^ 1);
                /**
                 * �ǿգ�˵���������ţ�����ֻ�ܱ���ȡ��
                 */
                best = cur.nexts[best] != null ? best : (best ^ 1);
                res |= (path ^ best) << move;
                cur = cur.nexts[best];
            }
            return res;
        }
    }

    public static int findMaximumXOR(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        NumTrie numTrie = new NumTrie();
        numTrie.add(arr[0]);
        System.out.println(Integer.toBinaryString(arr[0]));
        for (int i = 1; i < arr.length; i++) {
            System.out.println(Integer.toBinaryString(arr[i]));
            max = Math.max(max, numTrie.maxXor(arr[i]));
            numTrie.add(arr[i]);
        }
        return max;
    }

}
